# -*- mode: org; -*-
#+TITLE: Emacs Usage Guide
#+AUTHOR: Zelphir Kaltstahl
#+EMAIL: zelphirkaltstahl@posteo.de
#+STARTUP: content indent align inlineimages hideblocks entitiesplain nologdone nologreschedule nologredeadline nologrefile
#+TODO: TODO WIP DEPRECATED | DONE
#+DATE: <2021-05-23 Sun>
#+KEYWORDS: software design flexibility book notes
#+LANGUAGE: English
#+PRIORITIES: A E E
#+EXCLUDE_TAGS: noexport
#+OPTIONS: ^:{}
#+OPTIONS: H:10
#+OPTIONS: toc:2
#+OPTIONS: tags:nil
#+OPTIONS: tasks:t
#+OPTIONS: H:6
#+OPTIONS: p:nil
#+OPTIONS: pri:nil
#+OPTIONS: prop:nil
#+OPTIONS: todo:t
#+OPTIONS: stat:nil
#+OPTIONS: |:t
#+OPTIONS: inline:nil
#+OPTIONS: date:t

* Prerequisites

#+NAME: imports
#+begin_src scheme :results output verbatim replace drawer :noweb yes
(import
 (ice-9 exceptions))
#+end_src

#+NAME: identity-def
#+begin_src scheme :results output verbatim replace drawer :noweb yes
(define identity
  (λ (anything) anything))
#+end_src

#+NAME: assert-def
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<imports>>


(define assert
  (λ (condition if-false-message)
    (cond
     [condition 'no-error]
     [else
      (raise-exception
       (make-exception
        (make-non-continuable-error)
        (make-exception-with-message
         (simple-format
          #f "~a ~a"
          "assertion error:" if-false-message))
        #;(make-exception-with-irritants (list dividend divisor))
        #;(make-exception-with-origin 'divide)))])))
#+end_src

* Function combinators

Function combinators are functions, which take functions as input and return
functions, which make use of the given functions, combining them in useful
ways. Functions have a range of valid input values and an output range of
values. Combinators combine functions in such a way, that the resulting
functions consider the input range and output range of the combined functions
naturally.

** Composition

For example there is the combinator of function composition:

#+NAME: compose-def
#+begin_src scheme :results output verbatim replace drawer :noweb yes
(define compose
  ;; take 2 functions
  (λ (outer inner)
    ;; return a function, which takes any number of
    ;; arguments.
    (λ (. args)
      ;; the combination, or function composition in this
      ;; case, which applies first the inner function and
      ;; then the outer function.
      (outer (apply inner args)))))
#+end_src

#+RESULTS: compose-def
:results:
:end:

*** Usage

Its usage could look like the following:

#+NAME: compose-usage
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<compose-def>>

(define times-2-plus-3
  (compose (λ (n) (+ n 3))
           (λ (n) (* n 2))))

(simple-format
 (current-output-port)
 "~a\n"
 (times-2-plus-3 4))
#+end_src

#+RESULTS: compose-usage
:results:
11
:end:

** Iterate

The ~iterate~ combinator makes use of the ~compose~ combinator internally,
giving an example of how combinators can be used to build other combinators.

#+NAME: iterate-def
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<identity-def>>

(define iterate
  (λ (n)
    "Return a function, which applies the given function n
times by composing it n times."
    (λ (iteratee)
      (let compose-iter ([iter-count 0])
        (cond
         [(= iter-count n) identity]
         [else
          (compose iteratee
                   (compose-iter (+ iter-count 1)))])))))
#+end_src

#+RESULTS: iterate-def
:results:
:end:

One important thing to note is, that neither ~compose~ nor ~iterate~ need to
know anything about the actual functions, which they are combining. They
constitute a separate abstraction layer, that deals with combining functions and
not with the actual implementation inside functions. In fact it would be
detrimental to the usage of combinators, if they had built in assumptions about
the functions, which they combine.

*** Usage

The usage of ~iterate~ is for example the following:

#+NAME: iterate-usage
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<iterate-def>>

(simple-format
 (current-output-port)
 "~a\n"
 (((iterate 3) (λ (n) (+ 7 n))) 0))
#+end_src

#+RESULTS: iterate-usage
:results:
21
:end:

** Parallel combine

The ~parallel-combine~ combinator takes a function (~func-1~), which combines
the results of 2 other functions (~func-2~ and ~func-3~). It is named parallel,
because the 2 other functions are evaluated independently and their results are
then used as inputs for ~func-1~. It does not relate to parallelism as in using
multiple cores. However, the structure of the combinator makes it possible to
evaluate ~func-2~ and ~func-3~ on separate cores, taking advantage of a multi
core system. Combinators make no assumption to be used on a single or multi core
machine.

#+name: parallel-combine-def
#+begin_src scheme :results output verbatim replace drawer :noweb yes
(define parallel-combine
  (λ (func-1 func-2 func-3)
    ;; function combinators return functions
    (λ (. args)
      (func-1 (apply func-2 args)
              (apply func-3 args)))))
#+end_src

#+RESULTS: parallel-combine-def
:results:
:end:

In simple terms: Take 3 functions. Return a function. That function does the
following: Take arguments. One of the functions applied to the results of the
other 2 functions when applied to the arguments.

Naturally this requires one of the other 2 functions to either be able to work
with arbitrary numbers of arguments, or both functions to be of the same arity.

*** Usage

The usage is as follows:

#+name: parallel-combine-usage
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<parallel-combine-def>>

(define sum-and-product
  (λ (a b)
    ((parallel-combine list
                       (λ (arg1 arg2) (+ arg1 arg2))
                       (λ (arg1 arg2) (* arg1 arg2)))
     a b)))

(simple-format
 (current-output-port)
 "~a\n"
 (sum-and-product 3 4))
#+end_src

#+RESULTS: parallel-combine-usage
:results:
(7 12)
:end:

** Spread combine

The combinator ~spread-combine~ requires, that there is a way of determining the
arity of a given function. Its idea is to make and return a function, which
takes all the arguments of 2 given functions ~f~ and ~g~ and then internally
split those arguments into the ones used by ~f~ and ~g~. To perform this split
or spread of the arguments, the resulting function needs to know how many
arguments are meant to be used for ~f~. Knowing that number of arguments, the
rest of the arguments will be given to ~g~. The results of ~f~ and ~g~ will be
used as 2 arguments for ~h~, which combines the results in some way.

In order to implement ~spread-combine~, first a mechanism for determining the
arity needs to be implemented. It is implemented here in a general way, by
passing functions inside structs, which carry the additional information. There
might be more language specific ways to do this, depending on the programming
language, that is used to implement the combinators for. Here we make use of
composition in form of structs, which we can extend to have more fields, if we
need to do so.

One disadvantage of this approach is, that it will affect how users can use the
function combinators. They will have to use special functions to work with the
structs instead of using the usual functions like ~apply~ on functions. However,
the functions each travelling with their own arity specification will prevent
usage of global state. It will therefore enable using the combinators
concurrently without mutex constructs.

#+name: arity-func-structs-def-1
#+begin_src scheme :results output verbatim replace drawer :noweb yes
(import
 ;; structs
 (srfi srfi-9)
 ;; for functional structs (not part of srfi-9 directly)
 (srfi srfi-9 gnu))


(define-immutable-record-type <arity-func>
  ;; define constructor
  (make-arity-func func min-arity max-arity)
  ;; define predicate
  arity-func?
  ;; define accessors and functional setters
  (func arity-func-func)
  (min-arity arity-func-min-arity set-arity-func-min-arity)
  (max-arity arity-func-max-arity set-arity-func-max-arity))


(define get-arity
  (λ (f)
    "return an arity, if it is clear from the min arity and max arity"
    (cond
     [(eqv? (arity-func-min-arity f)
            (arity-func-max-arity f))
      (arity-func-min-arity f)]
     [else #f])))


(define restrict-arity
  (λ (f min-arity max-arity)
    "set the arity of a function"
    (cond
     [(arity-func? f)
      (set-fields f
                  ((arity-func-min-arity) min-arity)
                  ((arity-func-max-arity) max-arity))]
     [else
      (make-arity-func f min-arity max-arity)])))


(define arity-func-apply
  (λ (f args)
    (let ([num-args (length args)])
      (cond
       [(and (>= num-args (arity-func-min-arity f))
             (<= num-args (arity-func-max-arity f)))
        (apply (arity-func-func f) args)]
       [else
        (raise-exception
         (make-exception
          (make-non-continuable-error)
          (make-exception-with-message
           (simple-format
            #f
            "wrong arity of ~a: min-arity: ~a, max-arity: ~a, number of supplied arguments: ~a"
            f (arity-func-min-arity f) (arity-func-max-arity f) num-args))
          (make-exception-with-origin 'arity-func-apply)
          (make-exception-with-irritants args)))]))))
#+end_src


#+name: spread-combine-def-1
#+begin_src scheme :results output verbatim replace drawer :noweb yes
(import
 (prefix (srfi srfi-1) srfi-1:))


<<arity-func-structs-def-1>>
<<assert-def>>


(define spread-combine
  (λ (h f g)
    (let* ([arity-of-f (get-arity f)]
           [arity-of-g (get-arity g)]
           [sum-arity (+ arity-of-f arity-of-g)])
      (define the-combinator
        (λ (. args)
          ;; always perform arity checks
          (assert (= (length args) sum-arity)
                  "in spread-combine: arity of supplied functions does not agree with number of supplied arguments")
          (let ([args-f (srfi-1:take args arity-of-f)]
                [args-g (srfi-1:drop args arity-of-f)])
            (h (arity-func-apply f args-f)
               (arity-func-apply g args-g)))))
      ;; restrict the resulting function's arity to be the sum of the arities of
      ;; the 2 given functions f and g
      (restrict-arity the-combinator sum-arity sum-arity))))
#+end_src

#+RESULTS: spread-combine-def-1
:results:
:end:

#+name: spread-combine-usage-1
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<spread-combine-def-1>>


(simple-format
 (current-output-port)
 "~a\n"
 (arity-func-apply
  (spread-combine list
                  (make-arity-func (λ (a b) (list 'foo a b)) 2 2)
                  (make-arity-func (λ (x y z ignored1 ignored2) (list 'bar x y z)) 5 5))
  '(1 2 3 4 5 6 7)))
#+end_src

#+RESULTS: spread-combine-usage-1
:results:
((foo 1 2) (bar 3 4 5))
:end:

* Exercises

** Compose with arity checks

#+NAME: compose-arity-def
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<arity-func-structs-def-1>>
<<assert-def>>


(define compose
  (λ (outer inner)
    (let ([min-arity-inner (arity-func-min-arity inner)]
          [max-arity-inner (arity-func-max-arity inner)])
      (define the-combinator
        (λ (. args)
          (let ([num-args (length args)])
            ;; check for arity
            (assert (and (>= num-args min-arity-inner)
                         (<= num-args max-arity-inner))
                    (simple-format
                     #f
                     "arity mismatch: Expected at least ~a arguments and at most ~a arguments. Received ~a arguments."
                     min-arity-inner max-arity-inner num-args))
            (assert (= (arity-func-min-arity outer) 1)
                    (simple-format
                     #f
                     "arity mismatch: outer function takes at least ~a arguments. Received 1 argument."
                     (arity-func-min-arity outer)))
            ;; then apply
            (arity-func-apply outer (list (arity-func-apply inner args))))))
      ;; restrict arity of the combinator
      (restrict-arity the-combinator min-arity-inner max-arity-inner))))
#+end_src

#+RESULTS: compose-arity-def
:results:
:end:

#+NAME: compose-arity-usage
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<compose-arity-def>>


(simple-format
 (current-output-port) "~a\n"
 (arity-func-apply
  (compose
   (make-arity-func (λ (c) (* c 10)) 1 1)
   (make-arity-func (λ (a b) (+ a b)) 2 2))
  '(3 4)))
#+end_src

#+RESULTS: compose-arity-usage
:results:
70
:end:

** Parallel combine with arity checks

#+NAME: parallel-combine-arity-def
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<arity-func-structs-def-1>>
<<assert-def>>


(define parallel-combine
  (λ (h f g)
    (let ([min-arity-f (arity-func-min-arity f)]
          [max-arity-f (arity-func-max-arity f)]
          [min-arity-g (arity-func-min-arity g)]
          [max-arity-g (arity-func-max-arity g)])

      (assert (and (>= max-arity-f min-arity-g)
                   (>= max-arity-g min-arity-f))
              (simple-format
               #f
               "arity mismatch: Minimum and maximum arities of ~a and ~a incompatible."
               f g))
      (define the-combinator
        (λ (. args)
          (let ([num-args (length args)])
            ;; check arity of given arguments
            (assert (and (>= num-args (max min-arity-f min-arity-g))
                         (<= num-args (min max-arity-f max-arity-g)))
                    (simple-format
                     #f
                     "arity mismatch: Combinator expects at least ~a arguments and at most ~a arguments. Received ~a arguments."
                     (max min-arity-f min-arity-g)
                     (min max-arity-f max-arity-g)
                     num-args))
            (h (arity-func-apply f args)
               (arity-func-apply g args)))))
      ;; declare arity for later inspection
      (restrict-arity the-combinator
                      (max min-arity-f min-arity-g)
                      (min max-arity-f max-arity-g)))))
#+end_src

#+RESULTS: compose-arity-def
:results:
:end:

#+name: parallel-combine-arity-usage
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<parallel-combine-arity-def>>


(simple-format
 (current-output-port)
 "~a\n"
 (arity-func-apply
  (parallel-combine list
                    (make-arity-func (λ (arg1) (+ arg1)) 1 1)
                    (make-arity-func (λ (arg1 arg2) (* arg1 arg2)) 2 2))
  (list 3 4)))
#+end_src

#+RESULTS: parallel-combine-arity-usage
:results:
ice-9/boot-9.scm:1669:16: In procedure raise-exception:
ERROR:
  1. &non-continuable
  2. &message: "assertion error: arity mismatch: Minimum and maximum arities of #<<arity-func> func: #<procedure 1b4cc40 at <unknown port>:120:37 (arg1)> min-arity: 1 max-arity: 1> and #<<arity-func> func: #<procedure 1b4cc50 at <unknown port>:121:37 (arg1 arg2)> min-arity: 2 max-arity: 2> incompatible."

Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.
scheme@(guile-user) [1]>
:end:

** Plan for handling minimum and maximum arity

The plan for handling minimum and maximum arity is to somewhere store the
minimum and maximum arity. In some programming languages the arity might not be
easily accessible. In order to still provide access to the arity, the functions
are wrapped in a struct ~arity-func~, which contains the arity
information. However, this requires special procedures to work with the
struct. Instead of ~apply~ ~arity-func-apply~ is used and arity functions cannot
be applied as usual functions would.

If one assumes to work with a programming language, where the minimum and
maximum arities are readily accessible for normal procedures, one would not need
to wrap the functions into an additional struct.

An alternative would be to use global state to store arity information, instead
of letting it travel inside a struct along with the function.

Instead of storing only one arity for a function both minimum and maximum arity
need to be stored.

** Spread combine with arity checks

#+NAME: spread-combine-arity-def
#+begin_src scheme :results output verbatim replace drawer :noweb yes
(import
 (prefix (srfi srfi-1) srfi-1:))


<<arity-func-structs-def-1>>
<<assert-def>>


(define spread-combine
  (λ (h f g)
    (let* ([min-arity-f (arity-func-min-arity f)]
           [max-arity-f (arity-func-max-arity f)]
           [min-arity-g (arity-func-min-arity g)]
           [max-arity-g (arity-func-max-arity g)])

      (define the-combinator
        (λ (. args)
          (let ([num-args (length args)])
            ;; perform arity checks
            (assert (and (>= num-args min-arity-f))
                    (simple-format
                       #f
                       "arity mismatch: insufficient arguments for ~a. Given ~a arguments."
                       f num-args))
            (assert (and (>= num-args min-arity-g))
                    (simple-format
                       #f
                       "arity mismatch: insufficient arguments for ~a. Given ~a arguments."
                       g num-args))

            ;; When there are minimum and maximum arity, it might be the case,
            ;; that we cannot find only a single answer to the question, how many
            ;; arguments f should consume and how many it should leave for
            ;; g. Instead there could be multiple possibilities. We choose the
            ;; convention, that f takes as many as possible, while still leaving
            ;; as many as needed for g to work.

            ;; Substract the minimum required arguments of g from the number of
            ;; arguments given to the combinator. This is the amount of
            ;; arguments f can at most take.
            (let ([num-remaining-args-for-f (- num-args min-arity-g)])
              ;; If the remaining number of arguments is too low for f, throw an
              ;; exception.
              (simple-format (current-output-port) "remaining args for f: ~a\n" num-remaining-args-for-f)
              (assert (>= num-remaining-args-for-f min-arity-f)
                      (simple-format
                       #f
                       "arity mismatch: insufficient arguments for ~a and ~a. Given ~a arguments."
                       f g num-args))
              (let ([args-f (srfi-1:take args num-remaining-args-for-f)]
                    [args-g (srfi-1:drop args num-remaining-args-for-f)])
                (simple-format (current-output-port) "args-f: ~a\n" args-f)
                (simple-format (current-output-port) "args-g: ~a\n" args-g)
                (h (arity-func-apply f args-f)
                   (arity-func-apply g args-g)))))))

      ;; restrict the resulting function's arity
      (restrict-arity the-combinator
                      (+ min-arity-f min-arity-g)
                      (+ max-arity-f max-arity-g)))))
#+end_src

#+name: spread-combine-arity-usage
#+begin_src scheme :results output verbatim replace drawer :noweb yes
<<spread-combine-arity-def>>


(simple-format
 (current-output-port)
 "~a\n"
 (arity-func-apply
  (spread-combine list
                  (make-arity-func (λ (a b) (list 'foo a b)) 2 2)
                  (make-arity-func (λ (x y z ignored1 ignored2) (list 'bar x y z)) 5 5))
  '(1 2 3 4 5 6 7)))
#+end_src

#+RESULTS: spread-combine-arity-usage
:results:
remaining args for f: 2
args-f: (1 2)
args-g: (3 4 5 6 7)
((foo 1 2) (bar 3 4 5))
:end:

* local variable definitions                                       :noexport:

# Local Variables:
# fill-column: 80
# org-babel-noweb-wrap-start: "<<"
# org-babel-noweb-wrap-end: ">>"
# org-confirm-babel-evaluate: nil
# End:
